package seqlist.link;

import seqlist.SeqList;

/**
 * @author yuisama
 * @date 2023/03/12 20:32
 * 单链表的实现
 **/
// 火车类
public class SingleLinkedList<E> implements SeqList<E> {
    private Node head; // 第一节车厢的地址
    private int size; // 车厢节点个数，保存的元素个数

    // 车厢类的定义，车厢作为火车的私有内部类，对外部完全隐藏
    private class Node {
        E val; // 保存的元素
        Node next; // 下一节车厢的地址
        Node(E val) {
            this.val = val;
        }
    }
    //  ----------------------------------

    // 在当前链表头部添加元素
    public void addFirst(E val) {
        // 要插入一个元素，首先要产生一个新节点
        Node node = new Node(val);
        // 将当前节点插入到链表中
        node.next = head;
        // 更新head的引用，指向当前的新节点
        head = node;
        size ++;
    }


    @Override
    public void add(E element) {
        add(size,element);
    }

    @Override
    public void add(int index, E element) {
        // 1.base case，边界判断
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add index illegal!");
        }
        // 2.判断没有前驱的情况
        if (index == 0) {
            addFirst(element);
            return;
        }
        // 3.确实是中间位置的插入，寻找待插入位置的前驱！
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        // prev走到待插入位置的前驱
        Node node = new Node(element);
        node.next = prev.next;
        prev.next = node;
        size ++;
    }

    @Override
    public E removeByIndex(int index) {
        // 1.base case
        if (!rangeCheck(index)) {
            throw new IllegalArgumentException("remove index illegal!");
        }
        // 2.判断头节点的删除问题
        if (index == 0) {
            Node node = head;
            head = head.next;
            node.next = null;
            size --;
            return node.val;
        }
        // 3.现在确实是中间位置的删除
        Node prev = head;
        for (int i = 0; i < index - 1; i++) {
            prev = prev.next;
        }
        Node node = prev.next;
        prev.next = node.next;
        node.next = null;
        size --;
        return node.val;
    }

    @Override
    public void removeByValue(E element) {
        // 1.base case
        if (head == null) {
            return;
        }
        // 2.判断头节点恰好是待删除的节点
        if (head.val.equals(element)) {
            head = head.next;
            size --;
            return;
        }
        // 3.此时头节点不为空其一定不是待删除的结点
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.val.equals(element)) {
                // prev走到了待删除节点的前驱位置
                prev.next = prev.next.next;
                size --;
                return;
            }
            prev = prev.next;
        }
        // 4.链表中没有待删除的节点
        System.out.println("当前链表中不存在值为" + element + "的节点");
    }

    @Override
    public void removeAllValue(E element) {
        // 1.base case
        if(head == null) {
            return;
        }
        // 2.若头节点就是待删除的节点且出现连续的待删除节点
        while (head != null && head.val.equals(element)) {
            head = head.next;
            size --;
        }
        if (head == null) {
            // 整个链表已经删除完了
            return;
        }
        // 3.头节点一定不是待删除的节点且链表不为空！
        // prev一定指向的不是待删除的结点~
        Node prev = head;
        while (prev.next != null) {
            if (prev.next.val.equals(element)) {
                // 此时prev就是待删除节点的前驱
                prev.next = prev.next.next;
                size --;
            }else {
                // 只有后继节点不是待删除的结点才能移动prev引用!
                prev = prev.next;
            }
        }
    }

    @Override
    public E set(int index, E element) {
        // 1.合法性校验
        if (!rangeCheck(index)) {
            throw new IllegalArgumentException("set index illegal!");
        }
        // 从前向后遍历走到index对应的元素
        Node x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        // 此时x就落在了待修改的节点位置
        E oldVal = x.val;
        x.val = element;
        return oldVal;
    }

    private boolean rangeCheck(int index) {
        if (index < 0 || index >= size) {
            return false;
        }
        return true;
    }

    @Override
    public E get(int index) {
        if (!rangeCheck(index)) {
            throw new IllegalArgumentException("get index illegal!");
        }
        Node x = head;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x.val;
    }

    @Override
    public boolean contains(E element) {
        return false;
    }

    @Override
    public int indexOf(E element) {
        return 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        // 从当前链表的第一个节点开始向后遍历，直到走到尾结点为止
        // 第一个节点head
        // 尾结点的next值 == null
        // while循环
//        Node temp = head;
//        while (temp != null) {
//            // 当前temp还有值没有访问
//            sb.append(temp.val);
//            sb.append("->");
//            if (temp.next == null) {
//                // 此时temp走到了尾结点
//                sb.append("NULL");
//            }
//            temp = temp.next;
//        }
        // for循环
        for (Node x = head;x != null;x = x.next) {
            sb.append(x.val);
            sb.append("->");
            if (x.next == null) {
                sb.append("NULL");
            }
        }
        return sb.toString();
    }
}